1. Đa dạng tổ hợp
Sức mạnh thực sự của các quan hệ truy hồi nằm ở phạm vi rộng lớn của các dãy số mà chúng điều khiển. Ví dụ, các số Stirling loại hai được xác định bởi:
$$S_{n+1,k} = S_{n,k-1} + nS_{n,k}$$
Chúng đếm số cách chia một tập hợp gồm $n+1$ phần tử thành $k$ tập con không rỗng. Tương tự, số Catalan ($C_n$) mô tả việc tam giác hóa các đa giác lồi—chia một ngũ giác lồi thành các tam giác bằng cách sử dụng các đường chéo không cắt nhau.
2. Mô hình hóa cấu trúc và hoán vị vô phương
Các quan hệ truy hồi cung cấp một khung vững chắc cho các bài toán đếm không hiển nhiên, chẳng hạn như hoán vị vô phương. Danh từ kỹ thuật của một hoán vị mà không có phần tử nào ở vị trí ban đầu là hoán vị vô phương ($D_n$).
Mối quan hệ cho hoán vị vô phương được cho bởi:
$$D_n - nD_{n-1} = (-1)^n$$
Hoặc thay vào đó: $D_n = (n-1)(D_{n-1} + D_{n-2})$. Điều này đếm số cách mà $n$ người có thể nhận lại chiếc mũ sai tại quầy gửi mũ.
3. Giới hạn tăng trưởng và độ phức tạp
Các quan hệ truy hồi định nghĩa cả những giải pháp siêu hiệu quả lẫn những trường hợp tính toán "bùng nổ":
- Phương pháp Chia để trị: Tìm kiếm nhị phân được mô hình hóa bởi $a_n = c a_{n/m} + d$, dẫn đến thời gian chạy logarit.
- Hàm Ackermann: Định nghĩa độ sâu đệ quy tăng nhanh hơn bất kỳ hàm đa thức hay hàm mũ nào: $$AO(x + 3, y, z + 1) = AO(x + 2, y, AO(x + 3, y, z))$$